"""
https://leetcode.cn/problems/maximum-width-of-binary-tree/description/

662. 二叉树最大宽度
中等
相关标签
premium lock icon
相关企业
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 None 节点，这些 None 节点也计入长度。

题目数据保证答案将会在  32 位 带符号整数范围内。

 

示例 1：


输入：root = [1,3,2,5,3,None,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,None,9) 。
示例 2：


输入：root = [1,3,2,5,None,None,9,6,None,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,None,None,None,None,None,7) 。
示例 3：


输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
 

提示：

树中节点的数目范围是 [1, 3000]
-100 <= Node.val <= 100

"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import List, Optional

from tree_node import TreeNode,build_tree_node


class Solution:

    """
    每个节点在每层的位置，最大数量是2^0到2^n,其中n=level-1
    可以分别计算每一层的宽度，之后计算最大宽度
    """
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:

        def calc_node_list_width(node_list:List[TreeNode])->int:
            start_idx=-1
            end_idx=-1
            # print([(_.val if _ else None) for _ in node_list])
            for i,node in enumerate(node_list):
                if node:
                    if start_idx==-1:
                        start_idx=end_idx=i
                    else:
                        end_idx=i
            return 0 if start_idx==-1 else end_idx-start_idx+1
        
        def calc_next_level(node_list):
            res=[]
            has_node=False
            node_len=0
            for node in node_list:
                if node:
                    has_node=True
                    node_len+=1
                    res.append(node.left)
                    res.append(node.right)
                elif has_node:
                    res.append(None)
                    res.append(None)
            print(res)
            return res[:node_len]

        max_width=0

        def itr_tree_level(node_list):
            cur_width=calc_node_list_width(node_list)
            if cur_width==0:
                return
            nonlocal max_width
            max_width=max(cur_width,max_width)
            next_node_list=calc_next_level(node_list)
            print([(_.val if _ else None) for _ in node_list])
            if next_node_list:
                itr_tree_level(next_node_list)


        itr_tree_level([root])     

        return max_width
    
if __name__=='__main__':
    # arr=[0,0,0,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None,None,0,0,None]
    arr=[1,2,3,4,5]
    root=build_tree_node(arr)

    s=Solution()
    res=s.widthOfBinaryTree(root)
    print(res)